
"""
111. 二叉树的最小深度
"""
import collections
import sys
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.count = 0
        self.res = sys.maxsize

    def minDepth1(self, root: Optional[TreeNode]) -> int:
        """
        方法1，遍历二叉树
        """
        if not root:
            return 0
        self.traverse(root)
        return self.res

    '''遍历二叉树'''
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            return
        # 前序位置
        self.count += 1
        if not root.left and not root.right:
            self.res = min(self.res, self.count)
        self.traverse(root.left)
        # 中序位置
        self.traverse(root.right)
        # 后序位置
        self.count -= 1

    def minDepth(self, root: Optional[TreeNode]) -> int:
        """
        方法2，分解二叉树
        方法定义，输入一个二叉树根节点，输出以当前根节点的二叉树的最小深度
        """
        if not root:
            return 0
        # 左子树最小深度
        left = self.minDepth(root.left)
        # 右子树最小深度
        right = self.minDepth(root.right)

        # 返回当前根节点的二叉树的最小深度
        if not root.left:
            return right + 1
        if not root.right:
            return left + 1
        return min(left, right) + 1

    def minDepth3(self, root: Optional[TreeNode]) -> int:
        """
        二叉树层序遍历
        """
        count = 0

        if not root:
            return count

        # 辅助队列(永远只存储一层节点)
        q = collections.deque()
        q.append(root)

        # 两个遍历，第一个遍历层数，第二个遍历每层的各个元素
        while q:
            count += 1
            # 控制节点数，保证每次while循环只取出一层
            size = len(q)

            for i in range(0, size):
                # 取出队列第一个元素
                cur = q.popleft()
                if not cur.left and not cur.right:
                    return count
                # 将当前节点的左右子节点存储到队列中，用于遍历下一层
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)

        return count

sl = Solution()
print(sl.minDepth(TreeNode(1)))